package map;

import java.util.*;

/**
 * 四数之和
 */
public class FourSum {

  static class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
      List<List<Integer>> ans = new ArrayList<>();
      if (nums == null || nums.length < 4) {
        return ans;
      }
      Arrays.sort(nums);
      Set<String> set = new HashSet<>();
      for (int i = 0; i <= nums.length - 4; ++i) {
        if (i != 0 && nums[i] == nums[i - 1]) {
          continue;
        }
        //当前i固定的情况下，最小的四个数都要大于target，就不用往后面走了
        if ((nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3]) > target) {
          break;
        }
        //当前i固定的情况下，最大的四个数都要小于target，可以结束当前i开始的循环了，增大i
        if ((nums[i] + nums[nums.length - 3] + nums[nums.length - 2] + nums[nums.length - 1]) < target) {
          continue;
        }
        for (int j = i + 1; j <= nums.length - 3; ++j) {
          int k = j + 1, l = nums.length - 1;
          while (k < l) {
            if ((nums[i] + nums[j] + nums[k] + nums[l]) > target) {
              --l;
            } else if ((nums[i] + nums[j] + nums[k] + nums[l]) == target) {
              List<Integer> list = addToListAndCheckIsRepeat(nums[i], nums[j], nums[k], nums[l], set);
              if (list != null) {
                ans.add(list);
              }
              ++k;
              --l;
            } else if ((nums[i] + nums[j] + nums[k] + nums[l]) < target) {
              while ((k < l) && (nums[i] + nums[j] + nums[k] + nums[l]) < target) {
                ++k;
              }
              if ((k < l) && (nums[i] + nums[j] + nums[k] + nums[l]) == target) {
                List<Integer> list = addToListAndCheckIsRepeat(nums[i], nums[j], nums[k], nums[l], set);
                if (list != null) {
                  ans.add(list);
                }
                ++k;
                --l;
              }
            }
          }
        }
      }
      return ans;
    }

    public List<Integer> addToListAndCheckIsRepeat(int i, int j, int k, int l, Set<String> set) {
      List<Integer> list = new ArrayList<>();
      String tmp = "" + i + j + k + l;
      if (!set.contains(tmp)) {
        set.add(tmp);
        list.add(i);
        list.add(j);
        list.add(k);
        list.add(l);
        return list;
      }
      return null;
    }
  }
}
